
#include <iostream>
using namespace std;

class MyLinkedList {
 public:
  struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int value) : val(value), next(nullptr) {}
    ListNode() = default;
  };

  MyLinkedList() : size_(0), dummy_(new ListNode) {}

  int get(int index) {
    if (index >= size_ || index < 0) return -1;
    ListNode* tmp = dummy_;
    for (int i = 0; i <= index; ++i) {
      tmp = tmp->next;
    }
    return tmp->val;
  }

  void addAtHead(int val) {
    ListNode* node = new ListNode(val);
    node->next = dummy_->next;
    dummy_->next = node;
    ++size_;
  }

  void addAtTail(int val) {
    ListNode* tmp = dummy_;
    for (int i = 0; i < size_; ++i) tmp = tmp->next;
    ListNode* node = new ListNode(val);
    tmp->next = node;
    node->next = nullptr;
    ++size_;
  }

  void addAtIndex(int index, int val) {
    if (index > size_) return;
    if (index == size_) {
      addAtTail(val);
      return;
    }
    ListNode* tmp = dummy_;
    for (int i = 0; i < index; ++i) {
      tmp = tmp->next;
    }
    ListNode* next = tmp->next;
    ListNode* node = new ListNode(val);
    tmp->next = node;
    node->next = next;
    ++size_;
  }

  void deleteAtIndex(int index) {
    if (index >= size_) return;
    ListNode* tmp = dummy_;
    for (int i = 0; i < index; ++i) {
      tmp = tmp->next;
    }
    ListNode* next = tmp->next;
    tmp->next = next->next;
    delete next;
    --size_;
  }
  void Print() const {
    ListNode* tmp = dummy_;
    while (tmp->next) {
      tmp = tmp->next;
      cout << tmp->val << " ";
    }
    cout << endl;
  }

 private:
  int size_;
  ListNode* dummy_;
};

void Test1() {
  MyLinkedList* linkedList = new MyLinkedList();
  linkedList->addAtHead(1);
  linkedList->addAtTail(3);
  linkedList->addAtIndex(1, 2);        //链表变为1-> 2-> 3
  cout << linkedList->get(1) << endl;  //返回2
  linkedList->Print();
  linkedList->deleteAtIndex(1);        //现在链表是1-> 3
  cout << linkedList->get(1) << endl;  //返回3
}
void Test2() {
  MyLinkedList* linkedList = new MyLinkedList();
  linkedList->addAtHead(7);
  linkedList->addAtHead(2);
  linkedList->addAtHead(1);
  linkedList->addAtIndex(3, 0);
  linkedList->deleteAtIndex(2);
  linkedList->Print();
  linkedList->addAtHead(6);
  linkedList->addAtTail(4);
  linkedList->Print();
  cout << linkedList->get(4) << endl;
  linkedList->addAtHead(4);
  linkedList->addAtIndex(5, 0);
  linkedList->addAtHead(6);
}
int main() {
  // Test1();
  Test2();
  return 0;
}
// LC:707. 设计链表